theorem, efficient universal Turing machine
efficient universal Turing machine
#complexity_theory
#complexity_theory
Theorem
There exists a TM such that for every , , where denotes the TM represented by .
Moreover, if halts on input within steps then halts within steps, where is a number independent of and depending only on 's alphabet size, and number of states.
References
- S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 20.
- https://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf